import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

public class BloomFilter {
	private BitSet bitset;
	private int bitSetSize;
	private double bitsPerElement;
	private int expectedNumberOfFilterElements; 
	private int numberOfAddedElements; 
	private int k; // number of hash functions
	
	static final Charset charset = Charset.forName("UTF-8");
	static final MessageDigest digestFunction = null;

	
	/**
	* Constructs an empty Bloom filter. 
	* The total length of the Bloom filter will be
	* c*n.
	*
	* @param c is the number of bits used per element.
	* @param n is the expected number of elements the filter will contain.
	* @param k is the number of hash functions used.
	*/
	public BloomFilter(double c, int n, int k) {
		this.expectedNumberOfFilterElements = n;
		this.k = k;
		this.bitsPerElement = c;
		this.bitSetSize = (int) Math.ceil(c * n);
		numberOfAddedElements = 0;
		this.bitset = new BitSet(bitSetSize);
		try {
			digestFunction.getInstance("MD5");
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
	}
	    
	/**
	* Constructs an empty Bloom filter. The optimal number of hash functions (k) is estimated from the total size of the Bloom
	* and the number of expected elements.
	*
	* @param bitSetSize defines how many bits should be used in total for the filter.
	* @param expectedNumberOElements defines the maximum number of elements the filter is expected to contain.
	*/
	public BloomFilter(int bitSetSize, int expectedNumberOElements) {
		this(bitSetSize / (double) expectedNumberOElements,
				expectedNumberOElements, (int) Math
						.round((bitSetSize / (double) expectedNumberOElements)
								* Math.log(2.0)));
	}
	
	/**
	* Returns the number of hash functions K.
	* K is the optimal number of hash functions.
	*
	* @return optimal k.
	*/
	public int getK() {
		return this.k;
	}
	
	/**
	* Sets all bits to false in the Bloom filter.
	*/
	public void clear() {
		bitset.clear();
		numberOfAddedElements = 0;
	}
	
	/**
	* Adds an object to the Bloom filter. The output from the object's
	* toString() method is used as input to the hash functions.
	*
	* @param element is an element to register in the Bloom filter.
	*/
	public void addNumber(int number) {
		add(Integer.toString(number).getBytes(charset));
	}
	
	 /**
	* Adds an array of bytes to the Bloom filter.
	*
	* @param bytes array of bytes to add to the Bloom filter.
	*/
	public void add(byte[] bytes) {
		int[] hashes = createHashes(bytes, this.k);
		for (int hash : hashes)
			this.bitset.set(Math.abs(hash % this.bitSetSize), true);
		this.numberOfAddedElements++;
	}
	
	public static int[] createHashes(byte[] data, int hashes) {
		int[] result = new int[hashes];

		int k = 0;
		byte input = 0;
		while (k < hashes) {
			byte[] digest;
			synchronized (digestFunction) {
				digestFunction.update(input);
				input++;
				digest = digestFunction.digest(data);
			}

			for (int i = 0; i < digest.length / 4 && k < hashes; i++) {
				int h = 0;
				for (int j = (i * 4); j < (i * 4) + 4; j++) {
					h <<= 8;
					h |= ((int) digest[j]) & 0xFF;
				}
				result[k] = h;
				k++;
			}
		}
		return result;
	}

	/**
	* Returns true if the element could have been inserted into the Bloom filter.
	* 
	* @param number number to check.
	* @return true if the number could have been inserted into the Bloom filter.
	*/
	public boolean containsTheNumber(int number) {
		return contains(Integer.toString(number).getBytes(charset));
	}
	
	/**
	* Returns true if the array of bytes could have been inserted into the Bloom filter.
	* 
	* @param bytes array of bytes to check.
	* @return true if the array could have been inserted into the Bloom filter.
	*/
	public boolean contains(byte[] bytes) {
		int[] hashes = createHashes(bytes, this.k);
		for (int hash : hashes) {
			if (!this.bitset.get(Math.abs(hash % this.bitSetSize))) {
				return false;
			}
		}
		return true;
	}
	
	public int getSize() {
		return this.bitSetSize;
	}
	
	public int countNumOfElements() {
		return this.numberOfAddedElements;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + this.bitSetSize;
		long temp;
		temp = Double.doubleToLongBits(this.bitsPerElement);
		result = prime * result + (int) (temp ^ (temp >>> 32));
		result = prime * result + ((bitset == null) ? 0 : bitset.hashCode());
		result = prime * result + this.expectedNumberOfFilterElements;
		result = prime * result + this.k;
		result = prime * result + this.numberOfAddedElements;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof BloomFilter))
			return false;
		BloomFilter other = (BloomFilter) obj;
		if (this.bitSetSize != other.bitSetSize)
			return false;
		if (Double.doubleToLongBits(this.bitsPerElement) != Double
				.doubleToLongBits(other.bitsPerElement))
			return false;
		if (this.bitset == null) {
			if (other.bitset != null)
				return false;
		} else if (!this.bitset.equals(other.bitset))
			return false;
		if (this.expectedNumberOfFilterElements != other.expectedNumberOfFilterElements)
			return false;
		if (this.k != other.k)
			return false;
		if (this.numberOfAddedElements != other.numberOfAddedElements)
			return false;
		return true;
	}
}
